package leetcode.D100.T46;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {
    // 一刷
    /*public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        boolean[] isUsed = new boolean[nums.length];
        for(int i=0; i<nums.length; ++i) {
            dfs(result, temp, nums, i, isUsed);
        }
        return result;
    }
    private void dfs(List<List<Integer>> result, LinkedList<Integer> temp, int[] nums, int idx, boolean[] isUsed) {
        isUsed[idx] = true;
        temp.addLast(nums[idx]);
        if(temp.size() == nums.length) {
            result.add((List<Integer>)temp.clone());
        } else{
            for(int i=0; i<nums.length; ++i) {
                if(!isUsed[i]) {
                    dfs(result, temp, nums, i, isUsed);
                }
            }
        }
        isUsed[idx] = false;
        temp.removeLast();
    }*/

    // 二刷
    /*public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        for(int i=0; i<nums.length; ++i)
            dfs(nums, results, temp, used, i);
        return results;
    }

    private void dfs(int[] nums, List<List<Integer>> results, LinkedList<Integer> temp, boolean[] used, int cur) {
        temp.add(nums[cur]);
        used[cur] = true;
        if (temp.size() == nums.length)
            results.add((List<Integer>) temp.clone());
        else {
            for(int i=0; i<nums.length; ++i) {
                if (!used[i])
                    dfs(nums, results, temp, used, i);
            }
        }
        temp.remove(temp.size()-1);
        used[cur] = false;
    }*/

    // 三刷
    /*public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        for (int i=0; i<nums.length; ++i)
            dfs(result, temp, nums, used, i);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> temp, int[] nums, boolean[] used, int cur) {
        temp.add(nums[cur]);
        used[cur] = true;
        if (temp.size() == nums.length)
            result.add(new ArrayList<>(temp));
        else {
            for (int i=0; i<nums.length; ++i) {
                if (used[i])
                    continue;
                dfs(result, temp, nums, used, i);
            }
        }
        used[cur] = false;
        temp.remove(temp.size()-1);
    }*/

    // 四刷
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> temp, int[] nums, boolean[] used) {
        if (temp.size() == nums.length) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i=0; i<nums.length; ++i) {
            if (used[i])
                continue;
            used[i] = true;
            temp.add(nums[i]);
            dfs(result, temp, nums, used);
            used[i] = false;
            temp.remove(temp.size()-1);
        }
    }
}